#include <stdio.h>

#define N 4
int a[N] = {3,7,5,9};

// 思路: 每次应该都和 pivot 交换
int partition(int start, int end)
{
    int i, j, pivot, tmp;
	i = start;
	j = end;
	pivot = a[start];
	//pPivot = start;

	while (i < j)
	{
		while (a[j] >= pivot && i < j)
			j--;
		if(i < j)
		{
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
			//pPivot = j;
			//j--;
		}
		
		while (a[i] <= pivot && i < j)
			i++;
		if(i < j)
		{
            tmp = a[j];
			a[j] = a[i];
            a[i] = tmp;
			//pPivot = i;
			//i++;
		}
		
	}
    //a[i] = pivot;
	return i-start+1;
}
/* 从start到end之间找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
	// 用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
	int i;
	i = partition(start,end);
	if (k == i)
		//返回找到的元素;
        return a[start+i-1];
	else if (k > i)
		//从后半部分找出第k-i小的元素并返回;
		return order_statistic(start+i, end, k-i);
	else
		//从前半部分找出第k小的元素并返回;
		return order_statistic(start, start+i-2, k);
}


int main(void)
{
    int k =3;
	int num = order_statistic(0, N-1, k);
	printf("the %dth number is %d.\n", k, num);

	return 0;
	
}
